package com.itheima.leetcode.od.b.dynamicprogramming;

import java.util.Arrays;
import java.util.Scanner;

/**
 * <h3>实力差距最小总和（最佳对手）</h3>
 * 题目描述
 * <p>
 * 游戏里面，队伍通过匹配实力相近的对手进行对战。但是如果匹配的队伍实力相差太大，对于双方游戏体验都不会太好。
 * 给定n个队伍的实力值，对其进行两两实力匹配，两支队伍实例差距在允许的最大差距d内，则可以匹配。要求在匹配队伍最多的情况下匹配出的各组实力差距的总和最小。
 * <p>
 * 输入描述
 * 第一行两个整数，n，d。队伍个数n。允许的最大实力差距d。
 * 2<=n <=50
 * 0<=d<=100
 * <p>
 * 第二行，n个整数，表示队伍的实力值，以空格分割。
 * 0<=各队伍实力值<=100
 * <p>
 * 输出描述
 * 输出一个整数，表示各组对战的实力差值的总和。若没有队伍可以匹配，则输出-1。
 * <p>
 * 示例1：输入输出示例仅供调试，后台判题数据一般不包含示例
 * <p>
 * 输入
 * <p>
 * 6 30
 * <p>
 * 81 87 47 59 81 18
 * <p>
 * 输出
 * <p>
 * 57
 * <p>
 * 示例2：输入输出示例仅供调试，后台判题数据一般不包含示例
 * <p>
 * 输入
 * <p>
 * 6 20
 * <p>
 * 81 87 47 59 81 18
 * <p>
 * 输出
 * <p>
 * 12
 * <p>
 * 示例3：输入输出示例仅供调试，后台判题数据一般不包含示例
 * <p>
 * 输入
 * <p>
 * 4 10
 * <p>
 * 40 51 62 73
 * <p>
 * 输出
 * <p>
 * -1
 */
public class MinimumSumOfStrengthDifference {
    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);
        // 处理输入
        int n = in.nextInt();
        int d = in.nextInt();
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = in.nextInt();
        }

        System.out.println(getResult(data, n, d));
    }

    private static int getResult(int[] data, int n, int d) {
        // 按照大小排序
        Arrays.sort(data);

        //pair个数
        int[] dp1 = new int[n + 1];
        //最小和
        int[] dp2 = new int[n + 1];

        for (int i = 2; i < n + 1; i++) {
            int tmp = 0;
            if (data[i - 1] - data[i - 2] <= d) {
                tmp += 1;
            }

            if (dp1[i - 2] + tmp > dp1[i - 1]) {
                dp1[i] = dp1[i - 2] + tmp;
                dp2[i] = dp2[i - 2] + data[i - 1] - data[i - 2];
            } else if (dp1[i - 2] + tmp < dp1[i - 1]) {
                dp1[i] = dp1[i - 1];
                dp2[i] = dp2[i - 1];
            } else {
                if (tmp == 1) {
                    dp2[i] = Math.min(dp2[i - 1], dp2[i - 2] + data[i - 1] - data[i - 2]);
                } else {
                    dp2[i] = Math.min(dp2[i - 1], dp2[i - 2]);
                }
                dp1[i] = dp1[i - 1];
            }
        }

        return dp1[n] == 0 ? -1 : dp2[n];
    }
}